Even number squared plus one

An even number squared plus one is either prime or can be divided by a previous (2n)^2+1

Last modified	2016-10-07
Lines	111

Parent directory Download CGIread sitemap Main page

Quick links: (none)

```
/*
```
```
 * 
```
```
 * Even number squared plus one.
```
```
 *
```

 * An even number squared plus one is either prime or can be divided

```
 * by a previous (2n)^2+1
```
```
 */
```
```
#include <stdint.h>
```
```
typedef struct prime0_item_s {
```
```
    struct prime0_item_s *next;
```
```
    uint64_t item;
```
```
} prime0_item;
```

void prime0_init(prime0_item **list, uint32_t *counter);

uint64_t prime0_iterate(prime0_item *list, uint32_t *counter);

```
/* SPLIT HERE */
```
```
#include <stdlib.h>
```

void prime0_init(prime0_item **list, uint32_t *counter)

```
{
```

    *list = malloc(sizeof(prime0_item));

```
    (*list)->next = NULL;
```
```
    (*list)->item = 5;
```
```
    *counter = 2;
```
```
}
```

uint64_t prime0_iterate(prime0_item *list, uint32_t *counter)

```
{
```
```
    register uint64_t number, d;
```
```
    uint64_t stop;
```
```
    char insert_here;
```
```
    prime0_item *item, *next;
```
```
    /* Step to the next even number */
```
```
    *counter += 2;
```

    /* MUST expand the counter before calculating the next candidate. */

```
    stop = (uint64_t) *counter;
```
```
    number = stop * stop + 1;
```
```
    /* Begin factorization */
```

    for (item = list; item; item = item->next)

```
    {
```
```
        d = item->item;
```
```
        if (d >= stop || 1 == number)
```
```
            break;
```
```
        while (0 == number % d)
```
```
            number /= d;
```
```
    }
```

    /* If number isn't one, it must be a new prime. */

```
    if (1 != number)
```
```
    {
```

        for (item = list; item; item=item->next)

```
        {
```

            /* Criteria for correct placement. */

```
            if (item->next)
```

                insert_here = item->next->item > number;

```
            else
```
```
                insert_here = 1;
```
```
            if (insert_here)
```
```
            {
```

                /* Insert the new prime */

```
                next = item->next;
```

                item->next = malloc(sizeof(prime0_item));

                item->next->item = number;

                item->next->next = next;

```
                break;
```
```
            }
```
```
        }
```
```
    }
```
```
    return number;
```
```
}
```
```
/* SPLIT HERE */
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
int main(int argc, char *argv[])
```
```
{
```
```
    uint32_t counter, stop;
```
```
    prime0_item *list, *item;
```
```
    char *ign;
```
```
    
```
```
    if (argc != 2)
```
```
    {
```
```
        fputs(
```

            "Usage: prime0 stop-number\n"

```
            "\n"
```

            "This program will print a list of primes that are factors\n"

            "to squared even numbers plus one.  stop-number will be the\n"

            "highest number that will be squared.\n"

```
            "",
```
```
            stderr
```
```
        );
```
```
        return 1;
```
```
    }
```
```
    
```
```
    stop = strtoul(argv[1], &ign, 0);
```
```
    
```
```
    prime0_init(&list, &counter);
```
```
    
```
```
    while (counter <= stop)
```
```
        prime0_iterate(list, &counter);
```
```
    
```

    for (item = list; item; item = item->next)

```
        printf("%llu\n", item->item);
```
```
}
```